Задача #R103C
Хасан и Особое Удаление
Дан массив \(a\) из \(n\) целых чисел. Определим функцию \(f(a)\) для массива как количество различных целых чисел в массиве \(a\).
Например, \(f([1, 2, 4, 4, 2]) = 3\) , так как в массиве три различных числа: \(\{1,2,4\}\).
Вам разрешено выполнить ровно одну операцию: выбрать подмассив длины \(k\) и удалить этот подмассив.
Например, если \(a =[1, 2, 4, 4, 2]\) и \(k = 2\),, то, удалив элементы с 3-го по 4-й, получаем массив \([1, 2, 2]\) , и\(f(a)=2\)
Вычислите \(\min(f(a))\) после выполнения операции.
В первой строке дано одно целое число:
\(t (1 ≤ t ≤ 10^4 )\) – количество тестов.
Первая строка каждого теста содержит два целых числа:
\(n\) и \(k\) (\(1 ≤ k < n ≤ 2·10^5 \)) – соответственно длина массива и длина подмассива для удаления.
Вторая строка каждого теста содержит
\(n\) целых чисел:
\(a_1,a_2,..,a_n\) (\(1 ≤ a_i ≤ 10^{11} \)).
Гарантируется, что сумма \(n\) не превышает \(4 · 10^5\).
Для каждого теста нужно вывести одно целое число:
\(\min(f(a))\).
| # | input.txt | output.txt |
|---|---|---|
| 1 |
4 3 2 1 2 3 5 2 1 2 4 4 2 6 1 1 1 4 5 1 4 10 3 2 1 4 7 4 8 3 6 4 7 |
1 2 2 4 |
Для первого теста:
Какой бы подмассив вы ни выбрали, результат всегда будет равен \(1\).
Для второго теста:
Существует два способа выбрать подмассив: \([1,2]\) или \([4,4]\),
и в обоих случаях полученный массив будет содержать \(2\) различных числа.
Для четвертого теста:
Вам нужно выбрать \([8,3,6]\) и получившийся массив будет
\([2,1,4,7,6,4,7]\), в этом случае значение будет равно \(4\).
канал в Telegram, чтобы получать последние новости